A multi-bit adder is a circuit that receives two multi-bit binary input values and generates a multi-bit binary sum value corresponding to the sum of the two input values. Two conventional types of multi-bit adders are ripple-carry adders and look-ahead carry adders.
FIG. 1 shows a block diagram of conventional 4-bit ripple-carry adder 100, which receives two 4-bit binary input values (A3 A2 A1 A0) and (B3 B2 B1 B0) and generates a corresponding 5-bit binary sum value (C4 SUM3 SUM2 SUM1 SUM0), where A3, B3, and C4 are the most-Significant bits (MSBs) and A0, BO, and SUM0 are the least-significant bits (LSBs) of the three binary values, respectively.
Ripple-carry adder 100 comprises four 1-bit adders 101-104 connected serially from LSB adder 101 to MSB adder 104. Each 1-bit adder receives three 1-bit input values Ai, Bi, and Ci and generates 1-bit sum bit SUMi and 1-bit carry bit Ci+1, according to Equations (1) and (2) as follows:SUMi=Ai XOR Bi XOR Ci  (1)Ci+1=Ai·Bi+(Ai XOR Bi)Ci  (2)where the “XOR” operator is the logical “exclusive OR” function, the “·” operator is the logical “AND” function, and the “+” operator is the logical “OR” function. Note that Ci is the ith carry bit, which is received from the previous 1-bit adder, while Ci+1 is the (i+1)th carry bit, which is applied to the subsequent 1-bit adder.
If adder 100 is operated, in a stand-alone manner, as a 4-bit adder, then carry bit CO is 0, and carry bit C4 is the MSB of the resulting multi-bit sum. Alternatively, one or more instances of 4-bit adder 100 can be connected in series to form a multi-bit adder, in which case, carry bit C0 corresponds to carry bit C4 from the previous instance of 4-bit adder 100 (if there is one), and carry bit C4 is applied as carry bit CO to the subsequent instance of 4-bit adder 100 (if there is one).
Adder 100 is referred to as a “ripple-carry” adder, because the carry bits ripple through adder 100 in a serial manner. In particular, the carry-in bit (CIN in FIG. 1) received at each 1-bit adder is not valid until after the previous 1-bit adder has generated its carry-out bit (COUT). As such, adder 102 must wait until adder 101 has completed its implementation of Equation (2) before it can complete its implementation of Equations (1) and (2). Similarly, adder 103 must wait until adder 102 has completed its implementation of Equation (2) before it can complete its implementation of Equations (1) and (2). Lastly, adder 104 must wait until adder 103 has completed its implementation of Equation (2) before it can complete its implementation of Equations (1) and (2). This results in an inherent limitation to the speed at which a ripple-carry adder can generate its multi-bit output sum value, which speed decreases as the number of bits increases.
To overcome the processing-speed limitations associated with ripple-carry adders, look-ahead carry adders may be used.
FIG. 2 shows a block diagram of conventional 4-bit look-ahead carry adder 200, which, like 4-bit ripple-carry adder 100 of FIG. 1, receives two 4-bit binary input values (A3 A2 A1 A0) and (B3 B2 B1 B0) and generates a corresponding 5-bit binary sum value (C4 SUM3 SUM2 SUM1 SUM0).
Like ripple-carry adder 100, look-ahead carry adder 200 comprises four 1-bit adders 201-204 connected serially from LSB adder 201 to MSB adder 204, where each 1-bit adder receives three 1-bit input values Ai, Bi, and Ci and two 1-bit values SUMi and Ci+1 are generated according to Equations (1) and (2). Unlike, ripple-carry adder 100, however, look-ahead carry adder 200 includes look-ahead carry generation logic 205, which generates carry bits C1-C4 in parallel with the processing of 1-bit adders 201-204.
Look-ahead carry adder 200 takes advantage of the fact that carry bit Ci+1 generated by the ith 1-bit adder has a value of 1 only (i) if both bits Ai and Bi are a 1 or (ii) if only one of bits Ai and Bi is a 1 and carry bit Ci from the previous 1-bit adder is also a 1. Thus, carry bit Ci+1 may be re-defined from Equation (2) according to Equation (3) as follows:Ci+1=Gi+Pi·Ci  (3)where generate bit Gi and propagate bit Pi are defined according to Equations (4) and (5) as follows:Gi=Ai·Bi  (4)Pi=(Ai XOR Bi)  (5)
Substituting Equation (5) into Equation (1) yields an alternative formula for generating sum bit SUMi, according to Equation (6) as follows:SUMi=Pi XOR Ci  (6)
Substituting Equations (4) and (5) into Equation (2) to generate a formula for carry bit C1 yields Equation (7) as follows:C1=G0+P0·C0  (7)Substituting Equations (4), (5), and (7) into Equation (2) to generate a formula for carry bit C2 yields Equation (8) as follows:C2=G1+P1·G0+P1·P0·C0  (8)Continuing this pattern, formulas can be generated for carry bits C3 and C4 according to Equations (9) and (10) as follows:C3=G2+P2·G1+P2·P1·G0+P2·P1P0·C0  (9)C4=G3+P3·G2+P3··P2·G1+P3·P2·P1·G0+P3·P2·P1·P0·C0  (10)
Since (as indicated by Equations (4) and (5)) the propagate and generate bits, Pi and Gi, depend only on the input bits, Ai and Bi, and since (as indicated by Equations (7)-(10)) carry bits C1-C4 depend only on the propagate and generate bits, P0-P3 and G0-G3, and carry bit CO, the processing in look-ahead carry adder 200 can be implemented in the following three steps, where the operations within each step are implemented in parallel.
In the first step, each 1-bit adder implements Equations (4) and (5) to generate its propagate and generate bits, Pi and Gi, and provides those values to look-ahead carry generation logic 205. In the second step, look-ahead carry generation logic 205 implements Equations (7)-(10) to generate carry bits C1-C4. In the third step, each 1-bit adder implements Equation (6) to generate its corresponding sum bit SUMi.
In this way, 4-bit look-ahead carry adder 200 of FIG. 2 can operate faster than 4-bit ripple-carry adder 100 of FIG. 1, albeit at the added cost of implementing look-ahead carry generation logic 205, whose complexity increases as the number of bits increases.